package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author c2b
 * @since 2024/3/5 10:58
 */
public class LC0547 {
    static class Solution {
        /**
         * 深度优先遍历
         */
        public int findCircleNum(int[][] isConnected) {
            int cityCount = isConnected.length;
            boolean[] visited = new boolean[cityCount];
            int provinces = 0;
            for (int i = 0; i < cityCount; i++) {
                if (!visited[i]) {
                    dfs(isConnected, visited, cityCount, i);
                    ++provinces;
                }
            }
            return provinces;
        }

        private void dfs(int[][] isConnected, boolean[] visited, int cityCount, int i) {
            for (int j = 0; j < cityCount; j++) {
                if (isConnected[i][j] == 1 && !visited[j]) {
                    visited[j] = true;
                    dfs(isConnected, visited, cityCount, j);
                }
            }
        }

        /**
         * 广度优先遍历
         */
        public int findCircleNum2(int[][] isConnected) {
            int cityCount = isConnected.length;
            boolean[] visited = new boolean[cityCount];
            int provinces = 0;
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < cityCount; i++) {
                if (!visited[i]) {
                    queue.offer(i);
                    while (!queue.isEmpty()) {
                        Integer j = queue.poll();
                        visited[j] = true;
                        for (int k = 0; k < cityCount; k++) {
                            if (isConnected[j][k] == 1 && !visited[k]) {
                                queue.offer(k);
                            }
                        }
                    }
                    ++provinces;
                }
            }
            return provinces;
        }


        /**
         * 并查集
         */
        public int findCircleNum3(int[][] isConnected) {
            int cityCount = isConnected.length;
            int[] parent = new int[cityCount];
            for (int i = 0; i < cityCount; i++) {
                parent[i] = i;
            }
            for (int i = 0; i < cityCount; i++) {
                for (int j = i + 1; j < cityCount; j++) {
                    if (isConnected[i][j] == 1) {
                        union(parent, i, j);
                    }
                }
            }
            int provinces = 0;
            for (int i = 0; i < cityCount; i++) {
                if (parent[i] == i) {
                    ++provinces;
                }
            }
            return provinces;
        }

        private void union(int[] parent, int x, int y) {
            parent[find(parent, x)] = find(parent, y);
        }

        private int find(int[] parent, int x) {
            if (parent[x] != x) {
                parent[x] = find(parent, parent[x]);
            }
            return parent[x];
        }
    }
}
